package com.hch.algorithm.binarytree;


import com.hch.algorithm.stack.Stack;

/**
 * 二叉树的二叉链式实现
 * 三叉链式实现比二叉链式实现少一个查找父节点的方法
 * 实现过程中，需要使用的栈是我自己编写的栈，代码见我的blog文章：栈(Stack)的Java实现
 * <p>
 * 二叉树需要实现的方法：
 * 　　isEmpty()：判断树是否为空。
 * 　　clear()：清空二叉树。
 * 　　add(BTNode, T)：向指定节点添加指定的孩子。
 * 　　height()：计算二叉树的高度。
 * 　　size()：计算二叉树的大小。
 * 　　findNode()：查找包含指定数据的节点是否存在。
 * 　　findParent()：查找包含指定数据的节点的父节点。
 * 　　recursePreIterate()：递归先序遍历二叉树。
 * 　　recurseInIterate()：递归中序遍历二叉树。
 * 　　recursePostIterate()：递归后序遍历二叉树。
 * 　　circlePreIterate()：循环先序遍历二叉树。
 * 　　circleInIterate()：循环中序遍历二叉树。
 * 　　circlePostIterate()：循环后序遍历二叉树。
 * 　　 layerIterate()：层次遍历二叉树。
 */
public class BinaryTree<T> {
    /**
     * root：二叉树的根节点
     */
    private TreeNode root;//根节点

    /**
     * 两种构造方法
     */
    public BinaryTree() {//空构造方法
        root = null;
    }

    public BinaryTree(TreeNode root) {
        this.root = root;
    }

    public BinaryTree(T data) {//使用一个数据的构造方法
        root = new TreeNode(data);
    }

    /**
     * root 的 get() 方法和 set() 方法
     */
    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 判断树是否为空
     *
     * @return 树是否为空
     */
    public boolean isEmpty() {
        if (root == null) {//根节点为空
            return true;
        }
        return false;
        //简单的实现： return (root == null);
    }

    /**
     * 清空二叉树
     */
    public void clear() {
        root = null;
    }

    /**
     * 向二叉树中添加数据
     *
     * @param data 需要添加的数据
     */
    public void add(T data, TreeNode root) {
        if (root.getData() == null)//当前二叉树还是空树
            this.root = new TreeNode(data);//将添加的数据放入跟节点
        else
            add(root, new TreeNode(data));//将添加的数据放入非空二叉树中
    }

    /**
     * 向非空二叉树中添加数据的具体实现
     *
     * @param currentRoot 当前节点
     * @param addNode     需要添加的节点
     */
    private boolean add(TreeNode currentRoot, TreeNode addNode) {
        if (currentRoot.getLeft() == null) {//当前节点的左孩子为空
            currentRoot.setLeft(addNode);//将新节点设为该节点的左孩子
            return true;
        } else if (currentRoot.getRight() == null) {//当前节点的右孩子为空
            currentRoot.setRight(addNode);//将新节点设为该节点的右孩子
            return true;
        }
        return false;//两个节点都不为空，则不能添加
    }

    /**
     * 获取二叉树的高度
     *
     * @return 二叉树的高度
     */
    public int height() {
        return height(root);
    }

    /**
     * 获取以根节点为 root 的二叉树的高度
     *
     * @param root 当前根节点
     * @return 高度
     */
    private int height(TreeNode root) {
        if (root == null)
            return 0;
        int depthLeft = height(root.getLeft());//递归计算左子树高度
        int depthRight = height(root.getRight());//递归计算右子树高度
        if (depthLeft >= depthRight)//左子树高度不比右子树低
            return depthLeft + 1;//返回左子树高度加 1，因为需要把根节点也算进去
        else //左子树比右子树低
            return depthRight + 1;//返回右子树高度加 1，需要把根节点算进去
    }

    /**
     * 计算二叉树包含的节点数
     *
     * @return 二叉树的节点数
     */
    public int size() {
        return size(root);
    }

    /**
     * 计算根节点为 root 的二叉树的大小
     *
     * @param root 根节点
     * @return 根节点为 root 的二叉树的大小
     */
    private int size(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + size(root.getLeft()) + size(root.getRight());
    }

    /**
     * 查找包含指定数据的节点
     *
     * @param data 需要查找的数据
     * @return 包含指定数据的节点
     */
    public TreeNode findNode(T data) {
        return findNode(root, data);
    }

    /**
     * 查找包含指定数据的节点的详细实现。
     *
     * @param root 当前节点
     * @param data 需要查找的数据
     * @return 包含查找数据的节点
     */
    private TreeNode findNode(TreeNode root, T data) {
        if (root.getData().equals(data))//当前节点的数据即为查找数据
            return root;
        else if (root.getLeft() != null)
            return findNode(root.getLeft(), data);//递归遍历左子树
        else if (root.getRight() != null)
            return findNode(root.getRight(), data);//递归遍历右子树
        return null;//没找到，返回 null
    }

    /**
     * 查找指定数据所在节点的父节点
     *
     * @param data 指定的数据
     * @return 父节点
     */
    public TreeNode findParent(T data) {
        TreeNode child = new TreeNode(data);
        return findParent(root, child);
    }

    /**
     * 查找父节点的详细实现
     *
     * @param parent 父节点
     * @param child  指定的数据
     * @return 父节点
     */
    private TreeNode findParent(TreeNode parent, TreeNode child) {
        if ((parent == null) || (parent.getLeft() == null) || (parent.getRight() == null))//父节点为空，则返回空
            return null;
        if ((parent.getLeft().getData() == child.getData()) ||///父节点的左孩子的数据即为指定数据
                (parent.getRight().getData() == child.getData()))//父节点的右孩子的数据即为指定数据
            return parent;//返回父节点
        TreeNode p;
        if ((p = findParent(parent.getLeft(), child)) != null)//递归查找左子树
            return p;
        return findParent(parent.getRight(), child);//递归查找右子树
    }

    /**
     * 先序遍历
     */
    public void preIterate() {
        System.out.print("先序递归遍历：");
        recursePreIterate(root);
        System.out.println();

        System.out.print("先序循环遍历：");
        circlePreIterate(root);
        System.out.println();
    }

    /**
     * 递归先序遍历指定节点的树
     *
     * @param root 树的根节点
     */
    public void recursePreIterate(TreeNode root) {
        if (root == null)
            return;
        System.out.print(" " + root.getData());
        recursePreIterate(root.getLeft());
        recursePreIterate(root.getRight());
    }

    /**
     * 先序循环遍历指定根节点的树
     * 需要使用栈来实现
     * <p>
     * 这个过程可能难理解，最好的理解方式就是画图
     * 自己画一棵树，然后根据程序的每一句去走一遍，就可以很好地理解程序了。
     *
     * @param root 指定的根节点
     */
    public void circlePreIterate(TreeNode root) {
        Stack<TreeNode<T>> s = new Stack<>();
        TreeNode<T> current = root;//用于保存当前节点
        while ((current != null) || !s.isEmpty()) {
            while (current != null) {//当前节点不为空
                System.out.print(" " + current.getData());//将当前数据打印
                s.push(current);//再将当前节点入栈
                current = current.getLeft();//将current节点的左孩子设置为当前节点
            }
            //现在已经到了树的最左下角的节点
            if (!s.isEmpty()) {
                current = s.pop();//栈顶元素出栈
                current = current.getRight();//将栈顶元素设置为栈顶元素的右孩子
            }
        }
    }

    /**
     * 中序遍历
     */
    public void inIterator() {
        System.out.print("中序递归遍历：");
        recurseInIterate(root);
        System.out.println();

        System.out.print("中序循环遍历：");
        circleInIterate(root);
        System.out.println();
    }

    /**
     * 递归中序遍历根节点为 root 的树
     *
     * @param root 根节点
     */
    public void recurseInIterate(TreeNode root) {
        if (root == null)
            return;
        recurseInIterate(root.getLeft());//迭代遍历左子树
        System.out.print(" " + root.getData());//输出数据
        recurseInIterate(root.getRight());//迭代遍历右子树
    }

    /**
     * 循环中序遍历根节点为 root 的树
     * 需要使用栈来实现
     *
     * @param root 根节点
     */
    public void circleInIterate(TreeNode root) {

        TreeNode<T> current = root;//当前节点
        Stack<TreeNode<T>> s = new Stack<>();

        while ((current != null) || (!s.isEmpty())) {
            while (current != null) {//当前节点不为空
                s.push(current);//将当前节点入栈
                current = current.getLeft();//设置当前节点为current节点的左孩子
            }
            if (!s.isEmpty()) {
                current = s.pop();//将栈顶元素出栈
                System.out.print(" " + current.getData());//打印出栈节点的数据
                current = current.getRight();//设置当前节点为current节点的右孩子
            }
        }
    }

    /**
     * 后序遍历
     */
    public void postIterate() {
        System.out.print("后序递归遍历：");
        recursePostIterate(root);
        System.out.println();

        System.out.print("后序循环遍历：");
        circlePostIterate(root);
        System.out.println();
    }

    /**
     * 后序递归遍历根节点为 root 的树
     *
     * @param root 根节点
     */
    public void recursePostIterate(TreeNode root) {
        if (root == null)
            return;
        recursePostIterate(root.getLeft());
        recursePostIterate(root.getRight());
        System.out.print(" " + root.getData());
    }

    /**
     * 反转二叉树
     */
    TreeNode<T> invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.getRight();
        root.setRight(root.getLeft());
        root.setLeft(tmp);
        invertTree(root.getLeft());
        invertTree(root.getRight());
        return root;
    }

    //    将有序数组转化成二叉搜素树
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        if (nums.length == 1) {
            return new TreeNode(nums[0]);
        }
//        找到中间的树当成二叉树的中间树
        int mid = nums.length / 2;
        TreeNode tree = new TreeNode(nums[mid]);
        int[] nums1 = new int[mid];
        int[] nums2 = new int[nums.length - 1 - mid];
        for (int i = 0; i < mid; i++) {
            nums1[i] = nums[i];
        }
        for (int i = mid + 1; i < nums.length; i++) {
            nums2[i - mid - 1] = nums[i];
        }
        tree.setLeft(mid == 0 ? null : sortedArrayToBST(nums1));
        tree.setRight(mid == nums.length ? null : sortedArrayToBST(nums2));
        return tree;

    }

    /**
     * 后序循环遍历根节点为 root 的树
     * 需要使用两个栈来实现
     * 这个过程很难理解，建议自己画棵树，根据代码，自己在树上画一遍代码的执行过程
     *
     * @param root 根节点
     */
    public void circlePostIterate(TreeNode root) {
        int cannot = 0;//用作标记，表示当前节点不能出栈
        int can = 1;//用作标记，表示当前节点可以出栈
        Stack<TreeNode<T>> sNode = new Stack<>();//树的节点栈
        Stack<Integer> sInt = new Stack<>();//用于判断当前节点是其父节点的左孩子还是右孩子。
        TreeNode current = root;

        while ((current != null) || (!sNode.isEmpty())) {//当前节点不为空或节点栈不为空
            //先将节点沿树最左枝入栈
            while (current != null) {//当前节点不为空
                sNode.push(current);//将节点入栈
                sInt.push(cannot);//标记当前节点不能出栈
                current = current.getLeft();//将当前节点设置为current节点的左孩子
            }
            while ((!sNode.isEmpty()) && (sInt.top() == can)) {
                //节点栈不为空，且当前节点可以出栈
                sInt.pop();//将当前节点的标记出栈
                System.out.print(" " + sNode.pop().getData());//将当前节点出栈
            }
            if ((!sNode.isEmpty()) && (sInt.top() == cannot)) {
                //节点栈不为空，且栈顶节点不能出栈
                sInt.pop();//将栈顶节点的标记出栈
                sInt.push(can);//将栈顶节点的标记入栈，使当前节点可以出栈
                current = sNode.top().getRight();//将当前节点设置为栈顶节点的右孩子
            }
        }
        /**
         * 为什么需要标记一个节点是否可以出栈？
         * 答：一个节点 node 入栈时，在其后续入栈的是它的左孩子。
         *     当 node 变成栈顶元素时，还需要将其右孩子入栈，而 node 节点此时不能出栈。
         *     但 node 节点第二次变成栈顶元素时，就可以出栈了。
         *     因此需要标记一个节点是否可以出栈，从而使得节点可以在第一次变成栈顶元素时不会出栈。
         *     而在第二次变成栈顶元素时让其出栈。
         */
    }

    //    判断二叉搜索树是否合法
    public boolean isValidBST(TreeNode<Integer> root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode<Integer> root, TreeNode<Integer> min, TreeNode<Integer> max) {
        // base case
        if (root == null) return true;
        // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
        if (min != null && root.getData() <= min.getData()) return false;
        if (max != null && root.getData() >= max.getData()) return false;
        // 限定左子树的最大值是 root.val，右子树的最小值是 root.val

        return isValidBST(root.getLeft(), min, root) &&
                isValidBST(root.getRight(), root, max);
    }

    /**
     * 树的层次遍历，需要使用队列来实现。
     *
     * 过程的理解：首先，将根节点入队，队列不为空时，就处理队列里每个节点。
     * 然后，将队首节点出队，处理该节点；如果该节点有左右孩子，则将左右孩子都入队。
     *
     * 为什么这样就可以实现呢？
     * 答：我们从根节点开始说。根节点入队后，队列不为空了，就可以处理队列里的节点。
     * 　　第一次出队的是根节点，处理完根节点就会把根节点的左右孩子（如果都有）都入队。
     * 　　这时队列里就有了树的第二层节点，而且是从左往右依次排列的。
     * 　　第二次出队的是根节点的左孩子，处理完以后就会把这个节点的左右孩子（如果有）都入队。
     * 　　这时，队列里有两类节点：树的第二层节点（根节点的右孩子），树的第三层节点（根节点左孩子的左右孩子）。
     * 　　第三次出队的是根节点的右孩子，处理完该节点后就会把该节点的左右孩子（如果有）都入队。
     * 　　这时，队列里只有树的第三层节点，而且是从左往右依次排列。
     * 　　循环这个过程，直到树的最后一层，即完成了树的层次遍历。
     */
//    public void layerIterate(BTNode root){
//
//        ArrayQueue<BTNode<T>> queue = new ArrayQueue<>();//用于保存一个节点的左右孩子
//        BTNode<T> current = root;//设置当前节点为根节点
//
//        System.out.print("**层次遍历**：");
//
//        if (current != null)
//            queue.enQueue(current);//将根节点入队
//        while (!queue.isEmpty()){
//            current = queue.deQueue();//设置当前节点为队首的节点
//
//            System.out.print(" " + current.getData());//处理当前节点
//
//            if (current.getLeft() != null)//当前节点有左孩子
//                queue.enQueue(current.getLeft());//将当前节点的左孩子入队
//            if (current.getRight() != null)//当前节点有右孩子
//                queue.enQueue(current.getRight());//将当前节点的右孩子入队
//        }
//        System.out.println();
//    }
}